// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package types

import (
	"bytes"
	"fmt"
	"sort"

	"cmd/compile/internal/base"
	"cmd/internal/src"
)

var PtrSize int

var RegSize int

// 运行时中的切片由三个组件表示：
// 
// 类型切片结构{
// ptr不安全。指针
// len int 
// cap int 
// /}
// 
// 运行时中的字符串由两个组件表示：
// 类型字符串struct{
// ptr unsafe.Pointer 
// len int 
// }
// 
// 这些变量是这些结构的字段和大小的偏移量。
var (
	SlicePtrOffset int64
	SliceLenOffset int64
	SliceCapOffset int64

	SliceSize  int64
	StringSize int64
)

var SkipSizeForTracing bool

// typePos返回与t关联的位置。
// 这是t被声明或作为类型表达式出现的位置。
func typePos(t *Type) src.XPos {
	if pos := t.Pos(); pos.IsKnown() {
		return pos
	}
	base.Fatalf("bad type: %v", t)
	panic("unreachable")
}

// MaxWidth是目标体系结构上值的最大大小。
var MaxWidth int64

// CalcSizeDisabled表示计算类型的宽度和对齐是否安全。见CalcSize。
var CalcSizeDisabled bool

// 机器大小和舍入对齐是围绕
// 指针的大小，在betypeinit中设置（请参见../amd64/galign.go）。
var defercalc int

func Rnd(o int64, r int64) int64 {
	if r < 1 || r > 8 || r&(r-1) != 0 {
		base.Fatalf("rnd %d", r)
	}
	return (o + r - 1) &^ (r - 1)
}

// expandiface计算
// 扩展嵌入式接口为接口类型t设置的方法。
func expandiface(t *Type) {
	seen := make(map[*Sym]*Field)
	var methods []*Field

	addMethod := func(m *Field, explicit bool) {
		switch prev := seen[m.Sym]; {
		case prev == nil:
			seen[m.Sym] = m
		case AllowsGoVersion(t.Pkg(), 1, 14) && !explicit && Identical(m.Type, prev.Type):
			return
		default:
			base.ErrorfAt(m.Pos, "duplicate method %s", m.Sym.Name)
		}
		methods = append(methods, m)
	}

	{
		methods := t.Methods().Slice()
		sort.SliceStable(methods, func(i, j int) bool {
			mi, mj := methods[i], methods[j]

			// 按类型名（如果有）对嵌入类型进行排序。
			if mi.Sym == nil && mj.Sym == nil {
				return mi.Type.Sym().Less(mj.Type.Sym())
			}

			// 在嵌入类型之前对方法进行排序。
			if mi.Sym == nil || mj.Sym == nil {
				return mi.Sym != nil
			}

			// 按符号名对方法进行排序。
			return mi.Sym.Less(mj.Sym)
		})
	}

	for _, m := range t.Methods().Slice() {
		if m.Sym == nil {
			continue
		}

		CheckSize(m.Type)
		addMethod(m, true)
	}

	for _, m := range t.Methods().Slice() {
		if m.Sym != nil || m.Type == nil {
			continue
		}

		if m.Type.IsUnion() {
			continue
		}

		// 在1.18中，嵌入式类型可以是任何类型。在Go 1.17中，我们不允许
		// 嵌入除接口以外的任何内容。
		if !m.Type.IsInterface() {
			if AllowsGoVersion(t.Pkg(), 1, 18) {
				continue
			}
			base.ErrorfAt(m.Pos, "interface contains embedded non-interface, non-union %v", m.Type)
			m.SetBroke(true)
			t.SetBroke(true)
			// 添加到字段中，以便错误消息
			// 在打印t时包含已断开的嵌入类型。
			// TODO（mdempsky）：重新讨论此问题。
			methods = append(methods, m)
			continue
		}

		// 嵌入式接口：复制所有方法
		// （包括损坏的方法，如果有），并添加到t的
		// 方法集。
		for _, t1 := range m.Type.AllMethods().Slice() {
			f := NewField(m.Pos, t1.Sym, t1.Type)
			addMethod(f, false)

			// 检查后清除位置，以确保与类型2一致。
			f.Pos = src.NoXPos
		}

		// 检查后清除位置，以确保与类型2一致。
		m.Pos = src.NoXPos
	}

	sort.Sort(MethodsByName(methods))

	if int64(len(methods)) >= MaxWidth/int64(PtrSize) {
		base.ErrorfAt(typePos(t), "interface too large")
	}
	for i, m := range methods {
		m.Offset = int64(i) * int64(PtrSize)
	}

	t.SetAllMethods(methods)
}

func calcStructOffset(errtype *Type, t *Type, o int64, flag int) int64 {
	// 标志是0（接收器）、1（实际结构）或RegSize（输入/输出参数）
	isStruct := flag == 1
	starto := o
	maxalign := int32(flag)
	if maxalign < 1 {
		maxalign = 1
	}
	lastzero := int64(0)
	for _, f := range t.Fields().Slice() {
		if f.Type == nil {
			// 断开的字段，只需跳过它，以便其他有效字段
			// 获得宽度。
			continue
		}

		CalcSize(f.Type)
		if int32(f.Type.align) > maxalign {
			maxalign = int32(f.Type.align)
		}
		if f.Type.align > 0 {
			o = Rnd(o, int64(f.Type.align))
		}
		if isStruct { // 对于receiver/args/results，不设置，它取决于ABI 
			f.Offset = o
		}

		w := f.Type.width
		if w < 0 {
			base.Fatalf("invalid width %d", f.Type.width)
		}
		if w == 0 {
			lastzero = o
		}
		o += w
		maxwidth := MaxWidth
		// 在32位系统上，反射表施加额外的约束
		// 每个字段的起始偏移量必须适合31位。
		if maxwidth < 1<<32 {
			maxwidth = 1<<31 - 1
		}
		if o >= maxwidth {
			base.ErrorfAt(typePos(errtype), "type %L too large", errtype)
			o = 8 // 小但非零
		}
	}

	// 对于以零大小结尾的非零大小结构，我们在类型中添加了一个额外的填充字节。这种填充确保了
	// 获取零大小对象的地址不会产生指向堆中下一个对象的
	// 指针。见第9401期。
	if flag == 1 && o > starto && o == lastzero {
		o++
	}

	// 最终宽度为四舍五入
	if flag != 0 {
		o = Rnd(o, int64(maxalign))
	}
	t.align = uint8(maxalign)

	// 类型宽度仅包括返回到第一个字段的偏移量
	t.width = o - starto

	return o
}

// findTypeLoop搜索涉及
// 类型t的无效类型声明循环，并报告是否找到了一个循环。如果是，则路径包含
// 循环。
// 
// 路径指向用于跟踪类型序列的切片
// 已访问。使用指向片的指针可以使片容量增加并限制重新分配。
func findTypeLoop(t *Type, path *[]*Type) bool {
	// 我们实现了一个简单的DFS循环查找算法。这个
	// 可能更快，但类型循环很少。

	if t.Sym() != nil {
		// 声明的类型。检查在类型
		// 递归。
		// 声明中使用的类型表达式上是否存在循环和其他

		// 类型从包中导入，因此它不能是
		// 类型循环的一部分（否则该包应该有
		// 编译失败）。
		if t.Sym().Pkg != LocalPkg {
			return false
		}

		for i, x := range *path {
			if x == t {
				*path = (*path)[i:]
				return true
			}
		}

		*path = append(*path, t)
		if findTypeLoop(t.Obj().(TypeObject).TypeDefn(), path) {
			return true
		}
		*path = (*path)[:len(*path)-1]
	} else {
		// 匿名类型。在包含的类型上递归。

		switch t.Kind() {
		case TARRAY:
			if findTypeLoop(t.Elem(), path) {
				return true
			}
		case TSTRUCT:
			for _, f := range t.Fields().Slice() {
				if findTypeLoop(f.Type, path) {
					return true
				}
			}
		case TINTER:
			for _, m := range t.Methods().Slice() {
				if m.Type.IsInterface() { // 嵌入式接口
					if findTypeLoop(m.Type, path) {
						return true
					}
				}
			}
		}
	}

	return false
}

func reportTypeLoop(t *Type) {
	if t.Broke() {
		return
	}

	var l []*Type
	if !findTypeLoop(t, &l) {
		base.Fatalf("failed to find type loop for: %v", t)
	}

	// 旋转循环，以便最早的类型声明是第一个。
	i := 0
	for j, t := range l[1:] {
		if typePos(t).Before(typePos(l[i])) {
			i = j + 1
		}
	}
	l = append(l[i:], l[:i]...)

	var msg bytes.Buffer
	fmt.Fprintf(&msg, "invalid recursive type %v\n", l[0])
	for _, t := range l {
		fmt.Fprintf(&msg, "\t%v: %v refers to\n", base.FmtPos(typePos(t)), t)
		t.SetBroke(true)
	}
	fmt.Fprintf(&msg, "\t%v: %v", base.FmtPos(typePos(l[0])), l[0])
	base.ErrorfAt(typePos(l[0]), msg.String())
}

// CalcSize计算并存储t的大小和对齐方式。
// 如果设置了CalcSizeDisabled，并且尚未计算大小/对齐方式
// 则调用Fatal。
// 这用于防止后端的数据争用。
func CalcSize(t *Type) {
	// 启用类型检查跟踪时调用CalcSize不安全。
	// 见第33658期。
	if base.EnableTrace && SkipSizeForTracing {
		return
	}
	if PtrSize == 0 {
		// 假设这是一个测试。
		return
	}

	if t == nil {
		return
	}

	if t.width == -2 {
		reportTypeLoop(t)
		t.width = 0
		t.align = 1
		return
	}

	if t.widthCalculated() {
		return
	}

	if CalcSizeDisabled {
		if t.Broke() {
			// 从下面的致命调用中断无限递归
			return
		}
		t.SetBroke(true)
		base.Fatalf("width not calculated: %v", t)
	}

	// 如果中断的递归类型为
	// 再次被引用
	if t.Broke() && t.width == 0 {
		return
	}

	// 将CheckSize调用推迟到我们完成后
	DeferCheckSize()

	lno := base.Pos
	if pos := t.Pos(); pos.IsKnown() {
		base.Pos = pos
	}

	t.width = -2
	t.align = 0 // 0表示使用t.Width，在引导期间

	et := t.Kind()
	switch et {
	case TFUNC, TCHAN, TMAP, TSTRING:
		break

	// SimType==0 
	default:
		if SimType[t.Kind()] != 0 {
			et = SimType[t.Kind()]
		}
	}

	var w int64
	switch et {
	default:
		base.Fatalf("CalcSize: unknown type: %v", t)

	// 编译器特定的东西
	case TINT8, TUINT8, TBOOL:
		// bool是int8 
		w = 1

	case TINT16, TUINT16:
		w = 2

	case TINT32, TUINT32, TFLOAT32:
		w = 4

	case TINT64, TUINT64, TFLOAT64:
		w = 8
		t.align = uint8(RegSize)

	case TCOMPLEX64:
		w = 8
		t.align = 4

	case TCOMPLEX128:
		w = 16
		t.align = uint8(RegSize)

	case TPTR:
		w = int64(PtrSize)
		CheckSize(t.Elem())

	case TUNSAFEPTR:
		w = int64(PtrSize)

	case TINTER: // 实现为2个指针
		w = 2 * int64(PtrSize)
		t.align = uint8(PtrSize)
		expandiface(t)

	case TUNION:
		// 目前一直是接口的一部分，所以大小/对齐无关紧要。
		// 假装一个联合被表示为一个接口。
		w = 2 * int64(PtrSize)
		t.align = uint8(PtrSize)

	case TCHAN: // 实现为指针
		w = int64(PtrSize)

		CheckSize(t.Elem())

		// 在
		// 完成任何顶级递归类型后，生成伪类型以触发通道元素大小检查。
		t1 := NewChanArgs(t)
		CheckSize(t1)

	case TCHANARGS:
		t1 := t.ChanArgs()
		CalcSize(t1) // 以防万一
		// 确保t1的大小。Elem（）是在这一点上计算的。我们可以在这里使用CalcSize（），而不是CheckSize（），因为在处理假
		// （可能是递归）类型。
		// chanargs之前，将计算顶级
		CalcSize(t1.Elem())
		if t1.Elem().width >= 1<<16 {
			base.Errorf("channel element type too large (>64kB)")
		}
		w = 1 // 任何操作都可以

	case TMAP: // 实现为指针
		w = int64(PtrSize)
		CheckSize(t.Elem())
		CheckSize(t.Key())

	case TFORW: // 应该在
		reportTypeLoop(t)
		w = 1 // 任何操作都可以

	case TANY:
		// 不是真正的类型；使用前应更换。
		base.Fatalf("CalcSize any")

	case TSTRING:
		if StringSize == 0 {
			base.Fatalf("early CalcSize string")
		}
		w = StringSize
		t.align = uint8(PtrSize)

	case TARRAY:
		if t.Elem() == nil {
			break
		}

		CalcSize(t.Elem())
		if t.Elem().width != 0 {
			cap := (uint64(MaxWidth) - 1) / uint64(t.Elem().width)
			if uint64(t.NumElem()) > cap {
				base.Errorf("type %L larger than address space", t)
			}
		}
		w = t.NumElem() * t.Elem().width
		t.align = t.Elem().align

	case TSLICE:
		if t.Elem() == nil {
			break
		}
		w = SliceSize
		CheckSize(t.Elem())
		t.align = uint8(PtrSize)

	case TSTRUCT:
		if t.IsFuncArgStruct() {
			base.Fatalf("CalcSize fn struct %v", t)
		}
		w = calcStructOffset(t, t, 0, 1)

	// 创建假类型以供稍后检查
	// 触发函数参数计算。
	case TFUNC:
		t1 := NewFuncArgs(t)
		CheckSize(t1)
		w = int64(PtrSize) // 函数类型的宽度为指针

	// 函数为3个位置结构；
	// 计算它们的宽度作为副作用。
	case TFUNCARGS:
		t1 := t.FuncArgs()
		w = calcStructOffset(t1, t1.Recvs(), 0, 0)
		w = calcStructOffset(t1, t1.Params(), w, RegSize)
		w = calcStructOffset(t1, t1.Results(), w, RegSize)
		t1.extra.(*Func).Argwid = w
		if w%int64(RegSize) != 0 {
			base.Warn("bad type %v %d\n", t1, w)
		}
		t.align = 1

	case TTYPEPARAM:
		// TODO（danscales）-当我们不再需要
		// 在noder2中进行CalcSize（在noder中不应该需要）
		w = int64(PtrSize)
	}

	if PtrSize == 4 && w != int64(int32(w)) {
		base.Errorf("type %v too large", t)
	}

	t.width = w
	if t.align == 0 {
		if w == 0 || w > 8 || w&(w-1) != 0 {
			base.Fatalf("invalid alignment for %v", t)
		}
		t.align = uint8(w)
	}

	base.Pos = lno

	ResumeCheckSize()
}

// CalcStructSize计算s的大小，
// 填充s.Width和s.Align，
// 即使大小计算被禁用。
func CalcStructSize(s *Type) {
	s.width = calcStructOffset(s, s, 0, 1) // sets align 
}

// RecalcSize类似于CalcSize，但会重新计算t的大小，即使之前已经计算过。它不会重新计算其他
// 类型。
func RecalcSize(t *Type) {
	t.align = 0
	CalcSize(t)
}

func (t *Type) widthCalculated() bool {
	return t.align > 0
}

// 当一个类型的宽度应该已知时，我们调用CheckSize 
// 来计算它。在像
// 
// type T*struct{next T}
// 
// 这样的声明期间，有必要将结构宽度
// 的计算推迟到T被初始化为指向该结构的指针之后。
// 类似地，在导入处理过程中，在定义结构之前，可以使用结构。在这些情况下，调用
// DeferrCheckSize（）会停止宽度计算，直到调用
// ResumeCheckSize（），此时所有被延迟的
// CalcSize都会被执行。
// 仅当需要立即调用类型大小
// 时才应调用CalcSize。CheckSize确保
// 大小最终得到评估。

var deferredTypeStack []*Type

func CheckSize(t *Type) {
	if t == nil {
		return
	}

	// 函数arg structs不应被选中
	// 在封闭函数之外。
	if t.IsFuncArgStruct() {
		base.Fatalf("CheckSize %v", t)
	}

	if defercalc == 0 {
		CalcSize(t)
		return
	}

	// 如果尚未在deferredTypeStack上推送类型，则立即执行
	if !t.Deferwidth() {
		t.SetDeferwidth(true)
		deferredTypeStack = append(deferredTypeStack, t)
	}
}

func DeferCheckSize() {
	defercalc++
}

func ResumeCheckSize() {
	if defercalc == 1 {
		for len(deferredTypeStack) > 0 {
			t := deferredTypeStack[len(deferredTypeStack)-1]
			deferredTypeStack = deferredTypeStack[:len(deferredTypeStack)-1]
			t.SetDeferwidth(false)
			CalcSize(t)
		}
	}

	defercalc--
}

// PtrDataSize返回包含指针数据的t 
// 前缀的字节长度。这个偏移量之后的任何东西都是标量数据。
// 
// PtrDataSize仅为实际Go类型定义。
// 在编译器内部类型（例如TSSA、TRESULTS）上使用它是错误的。
func PtrDataSize(t *Type) int64 {
	switch t.Kind() {
	case TBOOL, TINT8, TUINT8, TINT16, TUINT16, TINT32,
		TUINT32, TINT64, TUINT64, TINT, TUINT,
		TUINTPTR, TCOMPLEX64, TCOMPLEX128, TFLOAT32, TFLOAT64:
		return 0

	case TPTR:
		if t.Elem().NotInHeap() {
			return 0
		}
		return int64(PtrSize)

	case TUNSAFEPTR, TFUNC, TCHAN, TMAP:
		return int64(PtrSize)

	case TSTRING:
		// struct{byte*str；intgo len；}
		return int64(PtrSize)

	case TINTER:
		// 结构{Itab*选项卡；void*数据；}或者
		// struct{Type*Type；void*data；}
		// 注意：请参阅typebits中的注释。Set 
		return 2 * int64(PtrSize)

	case TSLICE:
		if t.Elem().NotInHeap() {
			return 0
		}
		// struct{byte*数组；uintgo len；uintgo cap；}
		return int64(PtrSize)

	case TARRAY:
		if t.NumElem() == 0 {
			return 0
		}
		// t.NumElem（）>0 
		size := PtrDataSize(t.Elem())
		if size == 0 {
			return 0
		}
		return (t.NumElem()-1)*t.Elem().Size() + size

	case TSTRUCT:
		// 查找最后一个有指针的字段（如果有）。
		fs := t.Fields().Slice()
		for i := len(fs) - 1; i >= 0; i-- {
			if size := PtrDataSize(fs[i].Type); size > 0 {
				return fs[i].Offset + size
			}
		}
		return 0

	default:
		base.Fatalf("PtrDataSize: unexpected type, %v", t)
		return 0
	}
}
